///////////////////////////////////////////////////
/// tototoy Code
/// $Id: linklist.h 26 2009-09-25 13:26:15Z tonyjobmails $
/// $Date: 2009-09-25 21:26:15 +0800 (五, 2009-09-25) $
/// $Author: tonyjobmails $
/// $Revision: 26 $
/// E-mail: tonyjobmails@gmail.com
/// filename: linklist.h
/// function: 链表的实现
///////////////////////////////////////////////////

#ifndef __LINKLIST__H
#define __LINKLIST__H

#include <iostream>
#include <string>
#include "base.h"
#include "operate.h"
#include "character.h"

namespace tototoy
{
	using namespace base_type;

	/////////////////////////////////////////////////////////
	/////////////////////////////////////////////////////////
	/// 链表数据结构的定义
	///
	/// 链表结点结构
	template<typename _T>
	struct _node_linklist
	{
		_node_linklist()
		{
			next_ptr = NULL;
		}
		typedef _node_linklist<_T>* _next_point;
		_T data;							/// 数据部分
		_next_point next_ptr;						/// 指几下一个结点的指针
	};
	///
	/// 重载<<操作符
	template<typename _T>
	std::ostream& operator << (std::ostream &output, _node_linklist<_T>* &op_data)
	{
		if(op_data)
		{
			output << op_data->data;
		}
		return output;
	}
	/////////////////////////////////////////////////////////
	/////////////////////////////////////////////////////////
	
	
	/////////////////////////////////////////////////////////
	/////////////////////////////////////////////////////////
	/// 链表类<结点数据>
	/// 模板参数类型要实现重载符值运算符"="、重载相等运算符"=="
	template<typename _T>
	class link_list
	{
		private:
			typedef _node_linklist<_T> _node_type;
		public:
			link_list();
			~link_list();
			
			const _uint_16 get_length() const
			{
				return this->length;
			}

			bool insert_by_order(_T const &data, bool asc = true);			/// 按顺序插入
			bool insert_back(_T const &data);					/// 插入一个元素到最后位置
			bool insert_front(_T const &data);					/// 插入一个元素到开始位置
			bool insert_pos(_T const &data, _uint_16 const position);		/// 插入一个元素到指定位置
			
			bool delete_pos(_uint_16 const position);				/// 删除指定位置上的结点
			bool delete_front();							/// 删除头结点
			bool delete_back();							/// 删除尾结点
			bool delete_node(_T const &data);					/// 删除元素data
			bool delete_list();							/// 删除整个列表
			
			bool get_front_elem(_T &data) const;					/// 得到第一个元素
			bool get_front_elem_delete(_T &data);					/// 得到并删除第一个元素
			bool get_pos_elem(_uint_16 pos, _T &data) const;			/// 得到第N个元素
			
			_node_type* search_node(_T const &data);				/// 查找第一个data元素结点

			template<typename _T1>
			void traver_node(op::action<_node_type*, _T1> *operate = NULL);		/// 遍历链表，做相应操作

		private:
			_uint_16 length;							/// 链表长度
			_node_linklist<_T> *head;						/// 头结点指针
	};
	/////////////////////////////////////////////////////////
	/////////////////////////////////////////////////////////
	

	////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	///////////////////////////////////////////////////////华丽的加粗分割线/////////////////////////////////////////////////////
	////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////


	
	/////////////////////////////////////////////////////////
	/////////////////////////////////////////////////////////
	/// 以下是成员函数的定义
	///
	///////////////////////////////////////////
	/// @brief 链表构造函数
	template<typename _T>
	link_list<_T>::link_list()
	{
		this->length = 0;
		this->head = NULL;
	}
	///////////////////////////////////////////
	
	///////////////////////////////////////////
	/// @brief 链表析构函数
	template<typename _T>
	link_list<_T>::~link_list()
	{
		this->delete_list();
		this->length = 0;
	}
	///////////////////////////////////////////

	///////////////////////////////////////////
	/// @brief 按顺序插入(自行保证链表在插入之前和asc顺序是一致的)
	/// @param data：要插入的元素
	/// @param asc：true升序 false降序
	/// @return 成功与否
	template<typename _T>
	bool link_list<_T>::insert_by_order(_T const &data, bool asc)
	{
		_node_type *tmp = new _node_type;
		tmp->data = data;
		tmp->next_ptr = this->head;
		_node_type *pre = tmp;
		_node_type *node = this->head;

		while(node)
		{
			/// 找到位置
			if((asc && node->data > data) || (asc && node->data < data))
				break;
			pre = node;
			node = node->next_ptr;
		}

		pre->next_ptr = tmp;
		tmp->next_ptr = node;
		if(node == this->head)
			this->head = tmp;
		this->length++;
		return true;
	}
	///////////////////////////////////////////

	///////////////////////////////////////////
	/// @brief 插入一个元素到最后位置
	/// @param data 要插入的元素
	/// @return 成功与否
	template<typename _T>
	bool link_list<_T>::insert_back(_T const &data)
	{
		_node_type *node = this->head;
		_node_type *tmp = NULL;
		/// 找到最后一个结点
		while(node && node->next_ptr)
			node = node->next_ptr;

		/// node = (_node_type *)malloc(sizeof(_node_type));
		tmp = new _node_type;
		if(tmp)
		{
			tmp->data = data;
			tmp->next_ptr = NULL;
			if(!node)
			{
				this->head = tmp;
			}
			else
			{
				node->next_ptr = tmp;
			}
			this->length++;
			return true;
		}
		else
		{
			std::cout << "内存分配失败" << std::endl;
			return false;
		}
	}
	///////////////////////////////////////////
	
	///////////////////////////////////////////
	/// @brief 插入一个元素到开始位置
	/// @param data 要插入的元素
	/// @return 成功与否
	template<typename _T>
	bool link_list<_T>::insert_front(_T const &data)
	{
		/// _node_type *node = (_node_type *)malloc(sizeof(_node_type));
		_node_type *node = new _node_type;
		if(node)
		{
			node->data = data;
			node->next_ptr = this->head;
			this->head = node;
			this->length++;
			return true;
		}
		else
		{
			std::cout << "内存分配失败" << std::endl;
			return false;
		}
	}
	///////////////////////////////////////////
	
	///////////////////////////////////////////
	/// @brief 插入一个元素到指定位置(插入后为第pos个位置)
	/// @param data 要插入的元素
	/// @param pos 插入的位置
	/// @return 成功与否
	template<typename _T>
	bool link_list<_T>::insert_pos(_T const &data, _uint_16 const position)
	{
		if(position > 0)
		{
			_uint_16 pos = position;
			/// _node_type *insert = (_node_type *)malloc(sizeof(_node_type));
			_node_type *insert = new _node_type;
			if(insert)
			{
				insert->data = data;
				_node_type *pre = insert;
				pre->next_ptr = this->head;
				if(pos == 1)
				{
					this->head = insert;
					this->length++;
					return true;
				}
				while(pre)
				{
					if(--pos == 0)
					{
						insert->next_ptr = pre->next_ptr;
						pre->next_ptr = insert;
						this->length++;
						return true;
					}
					pre = pre->next_ptr;
				}
			}
			else
			{
				std::cout << "内存分配失败" << std::endl;
			}
		}
		return false;
	}
	///////////////////////////////////////////
	
	///////////////////////////////////////////
	/// @brief 删除指定位置上的结点(从1开始)
	/// @param pos 插入的位置
	/// @return 成功与否
	template<typename _T>
	bool link_list<_T>::delete_pos(_uint_16 const position)
	{
		if(position > 0)
		{
			_uint_16 pos = position;
			_node_type *pre = this->head;
			_node_type *node = this->head;
			while(pre && node)
			{
				if(--pos == 0)
				{
					if(pre == node)
						this->head = this->head->next_ptr;
					else
						pre->next_ptr = node->next_ptr;
					delete node;
					this->length--;
					return true;
				}
				pre = node;
				node = node->next_ptr;
			}
		}
		return false;
	}
	///////////////////////////////////////////
	
	///////////////////////////////////////////
	/// @brief 删除头结点
	/// @return 成功与否
	template<typename _T>
	bool link_list<_T>::delete_front()
	{
		if(this->head)
		{
			_node_type *node = this->head;
			this->head = this->head->next_ptr;
			delete node;
			this->length--;
			return true;
		}
		return false;
	}
	///////////////////////////////////////////
	
	///////////////////////////////////////////
	/// @brief 删除尾结点
	/// @return 成功与否
	template<typename _T>
	bool link_list<_T>::delete_back()
	{
		if(this->head)
		{
			_node_type *pre = this->head;
			_node_type *node = this->head;
			while(node->next_ptr)
			{
				pre = node;
				node = node->next_ptr;
			}
			pre->next_ptr = NULL;
			delete node;
			this->length--;
			return true;
		}
		return false;
	}
	///////////////////////////////////////////
	
	///////////////////////////////////////////
	/// @brief 删除元素data
	/// @return 成功与否
	template<typename _T>
	bool link_list<_T>::delete_node(_T const &data)
	{
		if(this->head)
		{
			_node_type *pre = this->head;
			_node_type *node = this->head->next_ptr;
			if(this->head->data == data)
			{
				this->head = this->head->next_ptr;
				delete pre;
				this->length--;
				return true;
			}
			while(node)
			{
				if(node->data == data)
				{
					pre->next_ptr = node->next_ptr;
					delete node;
					this->length--;
					return true;
				}
				pre = node;
				node = node->next_ptr;
			}
		}
		return false;
	}
	///////////////////////////////////////////
	
	///////////////////////////////////////////
	/// @brief 删除整个列表
	/// @return 成功与否
	template<typename _T>
	bool link_list<_T>::delete_list()
	{
		_node_type *node = this->head;
		while(this->head)
		{
			node = this->head;
			this->head = this->head->next_ptr;
			delete node;
			node = NULL;
		}
		this->length = 0;
		return true;
	}
	///////////////////////////////////////////
	
	///////////////////////////////////////////
	/// @brief 得到第一个元素
	/// @return 是否成功
	template<typename _T>
	bool link_list<_T>::get_front_elem(_T &data) const
	{
		if(this->head)
		{
			data = this->head->data;
			return true;
		}
		return false;
	}
	///////////////////////////////////////////
	
	///////////////////////////////////////////
	/// @brief 得到并删除第一个元素
	/// @return 是否成功
	template<typename _T>
	bool link_list<_T>::get_front_elem_delete(_T &data)
	{
		if(this->head)
		{
			data = this->head->data;
			if(this->delete_front())
				return true;
		}
		return false;
	}
	///////////////////////////////////////////

	///////////////////////////////////////////
	/// @brief 得到第pos个元素
	/// @return 是否成功
	template<typename _T>
	bool link_list<_T>::get_pos_elem(_uint_16 pos, _T &data) const
	{
		if(pos && this->length >= pos && this->head)
		{
			_uint_16 idx = 1;
			_node_type *node = this->head;
			while(idx++ < pos && node)
			{
				node = node->next_ptr;
			}
			if(node)
			{
				data = node->data;
				return true;
			}
		}
		return false;
	}
	///////////////////////////////////////////

	///////////////////////////////////////////
	/// @brief 查找第一个data元素结点
	template<typename _T>
	_node_linklist<_T>* link_list<_T>::search_node(_T const &data)
	{
		_node_type *node = this->head;
		while(node)
		{
			if(node->data == data)
			{
				return node;
			}
			node = node->next_ptr;
		}
		return NULL;
	}
	///////////////////////////////////////////

	///////////////////////////////////////////
	/// @brief 遍历链表，做相应操作
	/// @param operate：操作基类，是一个函数对象
	template<typename _T>
	template<typename _T1>
	void link_list<_T>::traver_node(op::action<_node_type*, _T1> *operate)
	{
		if(this->length && this->head)
		{
			_node_type *node = this->head;
			while(node)
			{
				if(operate)
					(*operate)(node);	/// 操作
				node = node->next_ptr;
			}
		}
	}
	///////////////////////////////////////////
	///
	/////////////////////////////////////////////////////////
	/////////////////////////////////////////////////////////


	////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	///////////////////////////////////////////////////////华丽的加粗分割线/////////////////////////////////////////////////////
	////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////


	/// 特化重载<<对linker的cout
	std::ostream& operator << (std::ostream &output, link_list<_character_type> const &op_data);

	/// 特化
};

#endif
